Wireless Mesh Networks
A wireless mesh network (WMN) is a communication network of nodes, e.g., radio nodes, arranged in a mesh topology. The deployment of WMNs is driven by many applications, including last-mile Internet delivery, distributed sensing, and smart grid network deployment.
FIG. 1 shows an example of the WMN 100, which includes a gateway node 110 and multiple client nodes 120. The gateway node is connected to a backhaul (not shown) using wired or wireless communication links. The gateway node communicates with multiple client nodes wirelessly 125. Data traffic in the WMN includes inward traffic 130 from the client nodes to the gateway node, outward traffic 140 from the gateway node to client nodes, and point-to-point traffic 150 between the client nodes.
Although client nodes in the WMNs are typically stationary, the quality of wireless links between an arbitrary pair of client nodes is in general unstable and varies with time due to fading effects and interference. This instability nature of wireless links requires intelligent routing protocol design for WMNs that can cope with link state changes, deliver data packets with reliability and low latency, and maintain simplicity and flexibility.
DAG Based Routing in WMNs
In wireless networks, a number of routing protocols use directed acyclic graphs (DAG) as an abstraction of the topology of the network in order to keep track of network state information. Example of DAG based routing protocol is IPv6 routing protocol for low power and lossy networks (RPL). RPL is currently under development by the Internet Engineering Task Force (IETF).
FIG. 2 show an example of the DAG 200. The DAG is a directed graph wherein all edges are oriented in such a way that no cycles exist. The RPL is a routing protocol based on the DAG topology. For each DAG created in RPL, there is a root node 210. The DAG root node typically is the gateway node in the WMN. All edges 220 in the DAG are oriented toward and terminating at the root node. Each node in the DAG is associated with a rank 230. The ranks of nodes along any path to the DAG root are monotonically decreasing to avoid cycles.
To construct the DAG, the gateway node issues a control message, i.e., a DAG Information Object (DIO). The DIO conveys information about the DAG. The information includes a DAGID to identify the DAG, rank information for client nodes, and objective function identified by an objective code point (OCP) that specifies the metrics used within the DAG and the method for computing the rank.
Each client node receiving the DIO message for the first time adds a sender of the DIO to a parent list of the client node, determine the client node own rank according to the OCP, and transmits the DIO message with updated rank information. In general, after the client node receives the DIO message, the node has the following options. The node can discard the DIO based on several criteria recommended by the RPL, or process the DIO to maintain a position in an existing DAG or improve position by obtaining a lower rank according to the OCP and current path cost.
After the DAG is constructed, each node is able to forward any inward traffic by selecting a parent as the next-hop node. As shown in FIG. 2, the node 0 has a rank 0, the nodes 1-3 have a rank 1, the nodes 4-7 have a rank 3, and the nodes 8-10 have a rank 4.
To support the outward traffic from the gateway node to a client node, the client node issues a control message called a Destination Advertisement Object (DAO). The information conveyed in the DAO includes the rank of nodes. The rank is used to determine a distance to the client node, and reverse route information recording the nodes along the outward path. After the DAO message is received by the gateway node from the client node, all intermediate nodes in the inward path indicated by the DAG are recorded in the reverse path information of the DAO message, and a complete outward path is determined from the gateway node to the client node.
DAG Based Routing for Smart Grid Networks
A smart grid delivers electricity from electric suppliers to homes using digital technology to control home appliances to save energy, reduce cost and increase reliability. The smart grid integrates information and communications technology with energy technology to permit two way power flow, to achieve seamless operation for electric generation, delivery, and end-use benefit, and to enable wide adoption of renewable energy and electric vehicles.
Currently, most electric suppliers use an Automated Meter Reading (AMR) system to collect data from electric meters. The AMR system is usually radio-frequency based, which provides one-way communications from meters to a data-reading device (via a gateway). The use of AMR saves utility providers the expense of periodic trips to each location to read a meter.
However, the smart grid systems are expected to go one step further and provide more features than AMR. An advanced smart grid system is expected to provide two-way communications that allow utilities to keep track of electricity usage, keep consumers informed of latest electricity prices, and perform remote utility management, all in real-time. One solution for enabling these functionalities is to deploy a multi-hop wireless mesh network that connects all the electric meters (within a certain area) to a gateway, which in turn is connected (possibly by wireline) to a control center that performs the management described above. Such a network is usually called an advanced metering infrastructure (AMI).
It is desired to provide DAG based routing for AMI networks.